package 牛客算法篇; /**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-23
 * Time:14:59
 */

/**
 *
 牛客算法篇:BM7 链表中环的入口结点
 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 数据范围： n≤10000n≤10000，1<=结点值<=100001<=结点值<=10000
 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
 可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
 输入描述：
 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
 返回值描述：
 返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
 示例1
 输入：
 {1,2},{3,4,5}
 返回值：

 说明
 返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
 */
public class EntryNodeOfLoop {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = pHead;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                ListNode outcome = dummy;
                while (outcome != slow){
                    outcome = outcome.next;
                    slow = slow.next;
                }
                return outcome;
            }
        }
        return null;
    }
}
